package Mysinglelist4;

public class test1 {
    //判断链表的回文结构
    public static boolean huiwen(mysinglelist4.ListNode Head){

        mysinglelist4.ListNode fast=Head;
        mysinglelist4.ListNode slow=Head;
        mysinglelist4.ListNode cur=Head;
        mysinglelist4.ListNode curNext=Head;
        //1.找到中间结点
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        //2.反转中间后面的链表
        cur=slow.next;
        while(cur!=null){
            //curNext就是给cur找后路的，应该先放前面
            curNext=cur.next;

            cur.next=slow;
            slow=cur;
            cur=curNext;
        }
        //3.再头尾双指针判断是否相等
        while (Head!= slow){
            if(Head.val!=slow.val){
                return false;
            }
            //这里是为偶数链表准备的
            if (Head.next == slow) {
                return true;
            }
            Head=Head.next;
            slow=slow.next;
        }
        return true;
    }



    public static void main(String[] args) {
        mysinglelist4 list1 = new mysinglelist4();
        list1.addEnd(10);
        list1.addEnd(20);
        list1.addEnd(40);

        list1.addEnd(30);

        list1.addEnd(40);
        list1.addEnd(20);
        list1.addEnd(10);

        mysinglelist4 list2 = new mysinglelist4();
        list2.addEnd(20);
        list2.addEnd(40);
        list2.addEnd(60);
        list2.addEnd(80);
        list2.addEnd(100);

        boolean huiwen = huiwen(list1.head);
        System.out.println(huiwen);
    }

}
